package _线性;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class _搜索 {
    // 二分查找，，统一写闭区间，，<=
    // 左闭右闭，终止条件是 l=r+1
    // 35：搜索插入位置:https://leetcode.cn/problems/search-insert-position/
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return l;
    }

    // 34：在排序数组中找第一个和最后一个元素
    public int[] searchRange(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int first = -1;
        int last = -1;
        // 找第一个等于target的l位置
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] == target) {
                first = mid;
                r = mid - 1; //重点
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        // 最后一个等于target的位置
        l = 0;  r = nums.length - 1;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] == target) {
                last = mid;
                l = mid + 1; //重点
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return new int[]{first, last};
    }
}